Skip to main content

Faithful Numbers

Problem Description​

A number is called faithful if you can write it as the sum of distinct powers of 7. e.g., 2457 = 7 + 72 + 74 . If we order all the faithful numbers, we get the sequence 1 = 70, 7 = 71, 8 = 70 + 71, 49 = 72, 50 = 70 + 72 . . . and so on. Given some value of N, you have to find the N'th faithful number.

Examples​

Example 1:

Input:
N = 3
Output:
8
Explanation:
8 is the 3rd Faithful number.

Example 2:

Input:
N = 7
Output:
57
Explanation:
57 is the 7th Faithful number.

Your Task​

You don't need to read input or print anything. Your task is to complete the function nthFaithfulNum() which takes an Integer N as input and returns the answer.

Expected Time Complexity: O(log(n))O(log(n))

Expected Auxiliary Space: O(log(n))O(log(n))

Constraints​

  • 1 ≤ n ≤ 10^5

Problem Explanation​

A number is called faithful if you can write it as the sum of distinct powers of 7. e.g., 2457 = 7 + 72 + 74 . If we order all the faithful numbers, we get the sequence 1 = 70, 7 = 71, 8 = 70 + 71, 49 = 72, 50 = 70 + 72 . . . and so on. Given some value of N, you have to find the N'th faithful number.

Code Implementation​

Written by @Ishitamukherjee2004

def get_nth_faithful_number(n):
faithful_numbers = []
power = 0
while len(faithful_numbers) < n:
num = 7 ** power
faithful_numbers.append(num)
for i in range(len(faithful_numbers) - 1):
faithful_numbers.append(num + faithful_numbers[i])
power += 1
return faithful_numbers[n - 1]

n = int(input("Enter the value of N: "))
print("The {}th faithful number is: {}".format(n, get_nth_faithful_number(n)))

Solution Logic:​

This solution works by generating faithful numbers on the fly and storing them in a vector. It starts with the smallest faithful number, 1 (which is 7^0), and then generates larger faithful numbers by adding powers of 7 to the previously generated numbers.

Time Complexity​

  • The function iterates through the array once, so the time complexity is O(nlogn)O(n log n).

Space Complexity​

  • The function uses additional space for the result list, so the auxiliary space complexity is O(n)O(n).